//题目:
// 给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。
// 你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

// 给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。
// 因为答案可能非常大，返回对 109 + 7 取余 后的结果。
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
    int MAX_VALUE=1e9+7;
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
    vector<vector<vector<int>>> dp;
public:
    int dfs(int m, int n, int maxMove, int Row, int Col)
    {
        if(Row==-1 || Col==-1 || Row==m || Col==n) return 1;

        if(maxMove==0)
        {
            dp[Row][Col][maxMove]=0;
            return 0;
        } 
        if(dp[Row][Col][maxMove]!=-1) return dp[Row][Col][maxMove];//记忆功能

        //计算从(row,col)位置走到边界的情况
        int ret=0;
        for(int i=0;i<4;i++)
        {
            int x=Row+dx[i],y=Col+dy[i];
            
            (ret+=dfs(m,n,maxMove-1,x,y))%=MAX_VALUE;
        }
        dp[Row][Col][maxMove]=ret;//记录数据

        return ret;
    }
    int findPaths(int m, int n, int maxMove, int Row, int Col) 
    {
        //法一：记忆化搜索
        dp.resize(m+1,vector<vector<int>>(n+1,vector<int>(maxMove+1,-1)));
        // return dfs(m,n,maxMove,Row,Col);

        //法二：动态规划
        //1.创建dp表————dp[k][i][j]表示：在最多移动k次球后，求位于(i,j)位置的情况有多少种
        vector<vector<vector<int>>> dp(maxMove+1,vector<vector<int>>(m,vector<int>(n)));
        //2.初始化
        dp[0][Row][Col]=1;
        //3.填表————动态转移方程:if((i,j)是边界)ret+=count;else dp[i+1][x][y]=count+1;
        int ret=0;
        for(int k=0;k<maxMove;k++)
        {
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<n;j++)
                {
                    int count=dp[k][i][j];
                    if(count!=0)
                    {
                        for(int pos=0;pos<4;pos++)
                        {
                            int x=i+dx[pos],y=j+dy[pos];
                            if(x==m || y==n || x==-1 || y==-1)
                                (ret+=count)%=MAX_VALUE;
                            else 
                                (dp[k+1][x][y]+=count)%=MAX_VALUE;
                        }
                    }
                }
            }
        }
        return ret;
    }
};